package class_06;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 拓扑排序
 * 
 * 拓扑排序算法 适用范围：要求有向图，且有入度为0的节点，且没有环
    1.将图中的所有节点全部记录到HashMap，入度为零的节点添加到zeroInQueue
    2.建立一个集合用来存放结果
    3.从zeroInQueue中弹出一个，遍历她的子节点
    4.将其子节点入度减一
    5.如果这个子节点的入度为零了，就将其放入到zeroInQueue中
原文链接：https://blog.csdn.net/qq_38238041/article/details/79698995
 * @author LOGAN
 * 过程
 *https://blog.csdn.net/qq_38984851/article/details/82844186
 */
public class Code_03_TopologySort {

	// directed graph and no loop
	public static List<Node> sortedTopology(Graph graph) {
		HashMap<Node, Integer> inMap = new HashMap<>();
		Queue<Node> zeroInQueue = new LinkedList<>();
		for (Node node : graph.nodes.values()) {
			inMap.put(node, node.in);
			if (node.in == 0) {
				zeroInQueue.add(node);
			}
		}
		List<Node> result = new ArrayList<>();
		while (!zeroInQueue.isEmpty()) {
			Node cur = zeroInQueue.poll();
			result.add(cur);
			for (Node next : cur.nexts) {
				inMap.put(next, inMap.get(next) - 1);
				if (inMap.get(next) == 0) {
					zeroInQueue.add(next);
				}
			}
		}
		return result;
	}
}
